|
A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages. The zipper was described by Gérard Huet in 1997. It includes and generalizes the gap buffer technique sometimes used with arrays. The zipper technique is general in the sense that it can be adapted to lists, trees, and other recursively defined data structures. Such modified data structures are usually referred to as "a tree with zipper" or "a list with zipper" to emphasize that the structure is conceptually a tree or list, while the zipper is a detail of the implementation. A layman's explanation for a tree with zipper would be an ordinary computer filesystem with operations to go to parent (often cd ..), and the possibility to go downwards (cd subdirectory). The zipper is the pointer to the current path. Behind the scenes the zippers are efficient when making (functional) changes to a data structure, where a new, slightly changed, data structure is returned from an edit operation (instead of making a change in the current data structure).==Example: Bidirectional list traversal== Many common data structures in computer science can be expressed as the structure generated by a few primitive constructor operations or observer operations. These include the structure of finite lists, which can be generated by two operations: *Empty: Constructs an empty list *Insert(x, L): Constructs a list by inserting value x in front of list L The list (2, 3 ) is then constructed as Insert(1, Insert(2, Insert(3, Empty))). It is possible to describe the location of a value in a list as the number of steps from the front of the list to that value. More formally, a location is the number of additional Insert operations used to construct the whole list, after a particular value was inserted. A context for a location in the list is constructed by recording not just the number of Insert operations, but all of the other information about them—namely, the values that were inserted. These are represented in a separate list that is reversed from the order of the original data structure. Specifically, the context of "3" in the list (2, 3 ) is represented as (1 ). A list with a zipper represents the entire structure, and a location within the structure. This is a pair consisting of the location's context, and the part of the structure that begins at the location. The list (2, 3, 4 ) with a reference to the "3" is represented as ((1 ), (4 )). With the list represented this way, it is easy to define efficient operations that move the location forward or backward and manipulate the list at that location, for example by inserting or removing items. Similarly, applying the zipper transformation to a tree makes it easy to insert or remove values at a particular location in the tree. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zipper (data structure)」の詳細全文を読む スポンサード リンク
|